package priv.pront.code.lanqiao.competition.course.date0328;

import java.util.Scanner;

public class 浪漫的礼物 {
    static int N;
    static int[] arr = {3, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 125, 128};
    static int[] countArr = {2, 2, 2, 3, 2, 4, 3, 2, 5, 4, 2, 3, 4, 2};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        if (N == 0 || N == 2) {
            System.out.println(1);
            return;
        } else if (N == 1) {
            System.out.println(0);
            return;
        }

        System.out.println(process(N));
    }

    private static int process(int N) {
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == N){
                return countArr[i];
            }
            if (N < arr[i]) {
                return Math.min(countArr[i] + arr[i] - N, countArr[i - 1] + N - arr[i - 1]);
            }
        }
        return -1;
    }
}
